package com.leetcode;

import java.util.ArrayList;

public class ThreeSum
{
	public ArrayList<ArrayList<Integer>> threeSum(int[] num)
	{
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (num.length >= 3)
		{
			bubbleSort(num);
			for (int i = 0; i < num.length - 2; i++)
			{
				int a = num[i];
				if (i != 0 && a == num[i - 1])
				{// i右移时的重复，ps：在这里开始还纠结i-1会有问题，这里注意短路逻辑判断
					continue;
				}
				int k = i + 1;
				int n = num.length - 1;
				while (k < n)
				{
					int b = num[k];
					/*
					 * if(i!=0&&a==b){//改后bug k++; continue; }
					 */
					int c = num[n];
					if (n != num.length - 1 && c == num[n + 1])
					{
						n--;
						continue;
					}
					if (b + a + c == 0)
					{
						ArrayList<Integer> al = new ArrayList<Integer>();
						al.add(a);
						al.add(b);
						al.add(c);
						result.add(al);
						// System.out.println("["+a+","+b+","+c+"]");
						n--;
						continue;
					}
					else if (a + b + c > 0)
					{
						n--;
					}
					else
					{
						k++;
					}
				}
			}
		}
		return result;
	}

	// 冒泡排序，不在算法思考范围
	public void bubbleSort(int[] array)
	{
		if (array.length == 0)
			return;
		for (int i = 0; i < array.length - 1; i++)
		{// i是计数标记
			for (int j = 0; j < array.length - i - 1; j++)
			{// 注意终止条件的判断,冒泡的亮点在于从头到尾一对一对比较
				if (array[j] > array[j + 1])
				{
					swap(array, j, j + 1);
				}
			}
		}
	}

	public void swap(int[] array, int i, int j)
	{
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
